1. Field of the Invention
The present invention relates generally to employing a bridge protocol for interconnecting two or more local area networks (LANs). More particularly the invention relates to apparatus and method, which is backward compatible with existing 802.1D Spanning Tree Bridge Protocol, for improving routing capability of spanning tree forwarding without a significant increase in complexity and which enables traffic prioritized path differentiation and provides load balancing by supporting alternate paths selected according to one of two or more priority values carried by a frame to be forwarded.
2. Background Information
A Local Area Network (LAN) is used to connect end stations together to provide communications. A single LAN permits a limited number of end stations, a limited size, and a limited amount of offered load. In this respect, LANs cannot grow beyond a certain limit. LANs may be interconnected via internetworking devices such as bridges and routers. These devices have different advantages and disadvantages depending on the internetworking environment. In the early days of internetworking, bridges were popular because they were much cheaper and faster than routers. In addition, bridges were used to support heterogeneous network layer protocols. The primitive computing technology of those days favored off-loading of work to larger servers using protocols that were optimized for LANs.
IEEE 802 Standards Committee has specified two bridge protocols. IEEE 802.1 group has issued the IEEE 802.1D Spanning Tree Bridge Protocol and IEEE 802.5 group has issued the Source Routing Bridge Protocol. Among these two schemes, IEEE 802.1D offers a better solution and has been studied more intensively. This approach is transparent to end stations and requires no modifications to the MAC layer of end stations. All the routing related operations are done in the bridges. Today, the IEEE 802.1D Spanning Tree Bridge Protocol is widely used for interconnecting the family of IEEE 802 standard LANs.
A bridge has several ports connecting to different LANs. A frame sent from one LAN to the other will typically go through one or more ports and bridges. As bridges are capable of filtering frames, they are useful for dealing with unnecessary broadcast traffic. Such a broadcast containment capability renders bridging a simple solution to implementing a virtual LAN. This bridged LAN environment should be transparent and looks like a single LAN to end users. The basic function of bridges is to forward MAC (Medium Access Control) frames from one LAN to another, therein providing an extension to the LAN without requiring any modification to the communications software in the end stations attached to the LANs. Bridges do not modify the content or format of the MAC frames they receive. The operation of bridges should not misorder or duplicate frames. Upper-layer protocol transparency is an advantage of bridging since bridges can rapidly forward traffic representing any network-layer protocol without having to examine upper-layer information.
The landscape for internetworking has evolved considerably with advances in high-speed network layer routing and data link layer switching technologies. Functionalities at the two layers are increasingly similar. While routers are generally more intelligent than bridges in terms of their dynamic routing capability, they are also more complicated to operate and costly to implement. Bridges have been designed to span a range of routing capabilities from dynamic source routing to static spanning tree forwarding, thereby allowing a trade-off between routing performance and protocol complexity. Although routers are becoming cheaper and faster than they used to be, they remain more complicated than bridges to operate because intermediate hops must still rise above the data link layer in the protocol stack. In spite of the common wisdom that IP has won the network layer, there are still going to be non-IP network layer protocols in the foreseeable future. On the other hand, while bridges are evolving to accommodate more and more network layer functionality, they will always support multiple network layer protocols.
An IP (Internet Protocol) address encodes both a network and a host on that network. Since it does not specify an individual end system, but a physical location in a network, the IP address of a host must change whenever it moves from one network to another. On the other hand, an IEEE 802 MAC address identifies an end system instead of a physical location in a network, and hence is always applicable to a host no matter where it is located in the network. Such portability of addresses is important particularly for mobility and the benefit of plug-and-play. Although new features, are emerging to minimize the need to configure and reconfigure IP addresses, these features can increase the cost and processing overhead of the system. DHCP (Dynamic Host Configuration Protocol), for example, provides a widely deployed framework for host registration and configuration. DHCP, however, was designed only for fixed hosts on physically secure LANs. DHCP is being extended to allow dynamic reconfiguration of a single host triggered by the DHCP server (e.g. a new IP address). Depending on the bandwidth of the network between server and client, the delay in the reconfiguration process can grow exponentially as failed retransmissions trigger exponential backoff.
The IEEE 802.1D specification defines a protocol architecture for MAC bridges and recommends formats for a globally administered set of MAC station addresses across multiple LANs.
FIG. 1 shows a bridge protocol architecture for a connection of two LANs via local 10 or remote 12, 14 bridging. Referring to the OSI (open systems interconnect) reference model, a bridge encompasses the first two layers, namely the Physical Layer (layer 1) and the Data Link Layer (layer 2). There are two sublayers in layer 2: Medium Access Control (MAC) sublayer and Logical Link Control (LLC) sublayer. Bridges operate relay functions on the MAC sublayer and interface with the LLC sublayer above through LLC service access points. By using bridges, a growing LAN can be partitioned into self-contained units for administrative or maintenance reasons, as well as to improve performance via load balancing and fault isolation. Bridges are typically used to interconnect LANs of the same type, such as the family of IEEE 802 LANs. Translation among different link-layer protocols is needed, however, when the interconnected LANs are not homogeneous (e.g., IEEE 802.3 and IEEE 802.5 type LANS), and interoperability is achieved by appropriate frame encapsulation.
A bridge relays individual MAC user data frames between separate MAC protocols of the bridged LAN connected to the ports of the bridge. A MAC entity for each port handles all the media access method dependent functions, i.e., MAC protocol and procedures, as specified in the relevant IEEE 802 standard for that MAC technology. Each bridge port receives and transmits frames to and from the LAN to which it is attached using the services provided by the individual MAC entity associated with that port. Each bridge port also functions as an end station providing MAC service to the LLC layer. All MAC entities communicating across a bridged LAN are uniquely identified by their respective 48-bit MAC addresses. A bridge may use a 48-bit MAC address, or a 16-bit locally administered MAC address. This bridge address must be unique within the extended LAN, and a single unique bridge identifier (ID) is derived from it for the operation of a bridge protocol. Each frame transmitted from a source end station to a destination end station carries the MAC addresses of the end stations respectively in the source and destination address fields of the frame""s MAC header. A frame that is to be relayed by every bridge to all its neighboring bridges in an extended LAN contains a bridge group MAC address in the destination address field of the frame""s MAC header.
In the IEEE 802.1D standard, a shortest path spanning tree with respect to a predetermined bridge, known as a root bridge, is used to interconnect LANs to form an extended LAN. The spanning tree is determined by bridges in the extended LAN via a distributed spanning tree algorithm. A frame sent from one LAN to another could follow a longer path on the spanning tree than necessary when there exists an alternative shorter path connecting them. Note that non-tree links, which are links that have not been selected by the 802.1D spanning tree algorithm, are not used to share the load of the traffic. The load around the root bridge may be heavy, and throughput is severely limited.
The three basic functions set forth in the present standards of an IEEE 802.1D bridge are:
1) frame forwardingxe2x80x94forward a frame received from one port to another port
2) learningxe2x80x94xe2x80x9clearnxe2x80x9d and xe2x80x9crememberxe2x80x9d which port to forward a frame
3) spanning tree algorithmxe2x80x94make sure activated links form no loop, i.e., the bridges and links form a spanning tree
Functions (1) and (2) above are performed with the help of a Forwarding Database, or Filtering Database, (see FIGS. 7-4 of IEEE 802.1D 1998 Edition), within each bridge. Each bridge keeps a Forwarding Database, hereafter denoted FD, that specifies which port to forward a data frame with a particular destination. If there is no such entry in the FD, the bridge forwards the frame through all ports except the port from which the frame originates. Whenever a frame from source s arrives from port p, the bridge marks in its FD that the forwarding port of s is p. As the learning process is simple, if there is a loop in the bridged LAN, a frame may be forwarded indefinitely around the loop. To avoid this undesirable feature, function (3) mentioned above is used to make sure the active topology among the bridges is always a tree so that there is a unique path between each pair of bridges. We refer to such a path herein as a tree path.
The spanning tree algorithm builds a unique shortest path tree rooted at the root bridge in a distributed manner. This root bridge is typically selected using bridge identifiers. A path connecting the root bridge and another bridge over the spanning tree is referred to as a root path associated with the bridge. By exchanging configuration messages, bridges identify the root bridge and select which ports to activate. For each LAN, a single bridge is elected among all bridges connected to the LAN to be the designated bridge, such that it is the bridge that is closest to the root bridge. In order to maintain an up-to-date spanning tree that reflects the underlying topology, the root bridge broadcasts configuration messages periodically over the spanning tree to all other bridges, for example, approximately every four (4) seconds.
The IEEE 802.1D standard defines two types of Bridge Protocol Data Unit (BPDU), namely Configuration BPDU and Topology Change Notification BPDU. Bridges send MAC frames containing Configuration BPDU to each other in order to communicate topology information and compute the spanning tree. Bridges send MAC frames containing Topology Change Notification BPDU up the spanning tree to inform the root bridge of topology changes. Each Configuration BPDU MAC frame includes a MAC header that contains a source MAC address and a destination MAC address. The source MAC address is the MAC address on the port of the bridge originating the Configuration BPDU MAC frame. The destination MAC address field carries the bridge group MAC address so that the Configuration BPDU MAC frame is received by all the bridges in the extended LAN. The information in the Configuration BPDU may be used by a bridge in preparing its own Configuration BPDU MAC frame. Each Configuration BPDU contains a BPDU Header and a set of BPDU Parameters. The BPDU Header consists of a Protocol Identifier field, a Protocol Version Identifier field and a BPDU Type field. The Protocol Identifier takes a specific value that identifies the Spanning Tree Bridge Protocol. The Topology Change Notification BPDU consists merely of a Protocol Identifier field, a Protocol Version Identifier field, and a BPDU Type field with a code reserved for this type. When a bridge detects a change in the active topology of the spanning tree, it sends a Topology Change Notification BPDU to the root bridge. The root bridge will then broadcast it to all bridges in the extended LAN. The encoding for the fields in the Configuration BPDU and the Topology Change Notification BPDU can be found in the IEEE standards.
In order to balance traffic load, extensions to the IEEE 802.1D Spanning Tree Bridge Protocol have been proposed to allow non-tree links to be used for frame forwarding under appropriate conditions. These extensions consider alternate paths that traverse at least one non-tree link.
To provide quality of service (QoS) in LANs, the IEEE 802.1p standard specifies priority queuing in bridges. This mechanism may be used to improve queuing delay experienced by some frames over that experienced by other frames. If the bulk of the delay on an end-to-end forwarding path is due to queuing delay in the bridges traversed by the path, then providing differentiated bridge queuing delay will be an effective means to support QoS in an extended LAN. On the other hand, if the bulk of the delay is due to cumulative transit delay across one or more LAN segments, then providing path differentiation for frames of different priorities may be a more effective way to enhance QoS since it depends on the number and performance characteristics of the LAN segments traversed.
A need remains for supporting multi-level traffic prioritization and improving load balancing in an extended LAN, while maintaining backward compatibility with the IEEE 802.1D standard.
A prior system, referred to as a Spanning Tree Alternate Route (STAR) Bridge Protocol was previously disclosed by the present inventors and is described in U.S. patent application Ser. No. 09/977,115. The prior invention is a QoS-based bridge protocol that is backward compatible with the IEEE 802.1D standard, such that existing bridges need not be modified and new bridges operate seamlessly with the existing standard. This prior system attempts to find and forward frames over shorter alternate paths relative to tree paths on the standard spanning tree, and makes use of the standard spanning tree for default forwarding as well as multicast and broadcast operations. Shorter alternate paths are determined on a best effort basis, and the shortest alternate path identified by the STAR Bridge Protocol is referred to as an enhanced forwarding path. The enhanced forwarding path is not necessarily a shortest path, but is provably shorter than its corresponding tree path. In one embodiment of our prior system, all frames sent from a source bridge to a destination bridge are forwarded over either a standard tree path or an enhanced forwarding path, but not both. In another embodiment of the prior system, all frames sent from a source bridge to a destination bridge are forwarded over standard tree paths by default, while frames of a predetermined class are forwarded over enhanced forwarding paths if these alternate paths are available. In the event that an enhanced forwarding path leads to a destination bridge in a direction that is opposite to the normal tree path forwarding direction, a data frame is encapsulated to avoid unintended frame dropping. To enable the discovery of enhanced forwarding paths, the STAR bridge protocol defines three additional processes that are different from the three existing bridge processes set forth in the IEEE 802.1D standard. STAR bridges can execute both the standard and the new processes. One new bridge process allows a STAR bridge to find and estimate the distance of a path from itself to another STAR bridge. The other two new bridge processes enable extended learning and enhanced forwarding by the STAR bridges. The new processes operate based on control information carried in newly defined bridge protocol data units that are exchanged among STAR bridges. The STAR bridge protocol may be enabled to use the standard spanning tree for low priority traffic while forwarding high priority frames on enhanced forwarding paths whenever they are available. As IEEE 802.1p standard provides eight (8) different priorities, it is desirable to provide more than two forwarding paths to support different QoS levels when these paths are available and can be found. No prior system, except for the STAR Bridge Protocol, is known to support path differentiation in an extended LAN. However, the STAR Bridge Protocol supports at most two different forwarding paths between each pair of STAR bridges.
One prior art technique teaches a method of distributed load sharing (DLS) to allow non-tree links satisfying certain topological constraints to be selected for frame forwarding. The DLS method does not guarantee that a forwarding path is no worse than its corresponding tree path for any additive metric considered. Another prior art technique teaches an extended and simplified version of the original DLS method known as Generalized DLS (GDLS), wherein any non-tree link may be used. In the GDLS method, a non-tree link is not used if its xe2x80x9cspeedxe2x80x9d is smaller than that of the corresponding tree path. Neither of the DLS method nor the GDLS method supports traffic prioritization.
In the Source Routing Bridge Protocol which is an IEEE standard, information on a forwarding path is included in the header of each frame and each bridge simply reads the header and forwards the frame accordingly. The responsibility of finding and selecting a suitable forwarding path is on the end stations, not the bridges. When an end station wants to send a frame, it first broadcasts a path discovery frame. The path is recorded in the frame as it travels across the bridged LAN. When the frame reaches the destination end station, the desired path is found and the frame, which has a complete path set forth therein, is sent back to the source end station. As this mechanism of finding forwarding paths is basically a flooding mechanism, it may generate a large number of frames for each forwarding path discovered. With this path forwarding mechanism of the Source Routing Bridge Protocol, a frame can always travel through a shortest path. However, transparency of end stations is sacrificed in order to achieve all pair shortest paths and load sharing.
Another prior art technique teaches a bridge architecture that has IP routing features. The proposed bridges, referred to as SmartBridges, exchange topology information to obtain a complete topology of bridges and LAN segments in the extended LAN. Once the complete topology is synchronized, the shortest path to every LAN can be found. This method employs a mechanism to determine which LAN each end station is connected to, and detects the movement of each end station from one LAN to another. In accordance with this technique, frames that are forwarded between end stations of known locations follow a shortest possible path in the extended LAN. This method does not support traffic prioritization, and is not backward compatible with the IEEE 802.1D standard.
Still another method dynamically creates a shortest path tree rooted at a given bridge using the IEEE 802.1D standard spanning tree as a default. In accordance with this method, which is referred to as Source Dependent Spanning Tree (SDST), some non-tree links are activated and some tree links are disabled on demand according to observed packet transit delay over those links. Information kept in the SDST bridges grows quadratically with the number of ports in the bridges. This method does not support traffic prioritization, and is not backward compatible with the IEEE 802.1 standard.
In still another method, referred to as Optimal-Suboptimal Routing (OSR), alternate paths that are shorter than their corresponding tree paths can be identified in a bridged LAN, provided all the bridges in the bridged LAN implement and execute the method. In each of these bridges, the cost to each known end station is kept for each port of the bridge. OSR is similar to a distance vector routing method. Topology information is kept by every bridge for every port. In order to be backward compatible with the IEEE 802.1D standard, OSR bridges are required to encapsulate original data frames in a new special frame format that is recognized only by OSR bridges. Without such a tunneling mechanism, the frames can interfere with the normal operation of the bridges in accordance with the IEEE 802.1D standard. Due to data frame encapsulation, a path found by the method may be longer than its corresponding tree path when there are bridges that do not execute the method. Also, this method does not support traffic prioritization.
Another method maintains distance vectors in bridges showing the length and forwarding direction of each shortest path to a particular LAN, not an end station. Mapping tables are used to map end stations to LANs. When a frame is received by a bridge, the bridge maps the destination end station to the destination LAN to which the destination end station is attached, and finds the forwarding port from the distance vector. Mapping tables are exchanged by means of flooding, which results in inefficient utilization of network resources. This method does not support traffic prioritization, and is not backward compatible with the IEEE 802.1D standard.
A need remains for a method of multipriority path differentiation and load balancing in an extended LAN, wherein the method can support more than two priorities and spreads traffic of different priorities over multiple alternate forwarding paths when alternate paths that are shorter than their corresponding tree paths can be found.
The present invention is a novel protocol which is able to forward frames on two or more alternate forwarding paths (including a tree path) according to frame priorities, provided at least one alternative forwarding path that is shorter than the tree path can be found. If no such alternative forwarding path can be found, the tree path is used as a default forwarding path. It is possible to have alternate forwarding paths from a source end station to a destination end station when agent bridges of the end stations exist and are located on different branches of the spanning tree wherein an agent bridge of an end station is the STAR bridge that is closest to the end station along the standard tree forwarding path to the root bridge on the spanning tree. In this case, a frame forwarded from the designated bridge of the source end station must go upstream on the tree to the nearest common ancestor of the designated bridges of the source and destination end stations. A key feature of the present invention is that the higher the priority of a frame, the smaller the number of hops over the upstream tree path, starting from the designated bridge of the source end station, the frame has to make before it is allowed to be forwarded over an available shorter alternate forwarding path. In addition, for a frame of a given priority, it should be more likely to be forwarded over an available shorter alternate forwarding path the more hops it has made. The invention ensures that the forwarding path of a higher priority frame between a pair of end stations is shorter than or the same as the forwarding path of a lower priority frame between the same pair of end stations.
The present invention is an extension of the STAR Bridge Protocol, which as described herein in detail, attempts to find and forward frames over enhanced forwarding paths, and makes use of the standard spanning tree for default forwarding. In the STAR Bridge Protocol, a frame that is sent from the agent bridge of a source end station to the agent bridge of a destination end station is forwarded over a tree path if an enhanced forwarding path is unavailable. Otherwise, in one embodiment, the frame is forwarded over an enhanced forwarding path leading from the agent bridge of the source end station, and in another embodiment, the frame is forwarded over the said enhanced forwarding path provided the frame belongs to a selected class. Should the frame be forwarded over a tree path, intermediate STAR bridges along the tree path are not able to forward the frame over any of the enhanced forwarding paths leading from themselves toward the destination bridge. In accordance with the present invention, each frame that is sent from the agent bridge of a source end station to the agent bridge of a destination end station may go over a tree path, an enhanced forwarding path leading from the agent bridge of the source end station, and a hybrid forwarding path, which is a concatenation of a partial tree path and an enhanced forwarding path leading from an intermediate STAR bridge. The hybrid forwarding path is shorter than its corresponding tree path. The bridge processes and storage requirements specified in the STAR Bridge Protocol are generally applicable to the present invention. However, the invention extends the path finding process and the STAR forwarding process, but not the STAR learning process in the STAR Bridge Protocol.
The present invention extends the path finding process in the STAR Bridge Protocol. A new SBPDU frame known as an Announcement frame, is sent once by every STAR bridge in the beginning of the path finding process. This frame is broadcast over the spanning tree. When a first STAR bridge receives an Announcement frame originated from a second STAR bridge, that first STAR bridge knows the tree forwarding port, next hop STAR bridge, and the number of intermediate STAR bridges on the tree path leading to that second STAR bridge and keeps this information in the Bridge Forwarding (BF) Table. In accordance with the present invention, this information is used in the STAR forwarding process.
The present invention modifies the STAR forwarding process in the STAR Bridge Protocol so that more than two alternate paths may be used for forwarding frames. In the original STAR Bridge Protocol, only agent bridges may decide which of a tree path and an enhanced forwarding path is used to forward a data frame. In this invention, some intermediate STAR bridges are required to make similar forwarding decisions. When a STAR bridge receives a frame from a child port and discovers that the frame has been traversing a tree path, it decides whether to forward the frame upstream to a tree neighbor or forward the frame over an enhanced forwarding path leading from said STAR bridge. It determines the forwarding port by the priority of the frame and the length of the tree path the frame has traversed. If the STAR bridge sends the frame to an ancestor STAR bridge, that ancestor STAR bridge must decide on its own whether to forward the frame to an enhanced forwarding path leading from itself to the agent bridge of the destination end station. Subsequently, each STAR bridge that receives the frame must also decide on its own whether to forward the frame to an enhanced forwarding path leading from itself to the agent bridge of the destination end station, provided that the frame is not already being forwarded on an enhanced forwarding path leading from a different STAR bridge. If a frame reaches the agent bridge of the destination end station without a detour over an enhanced forwarding path from any intermediate STAR bridge, the frame will end up being forwarded over a tree path.
The present invention supports multi-level traffic prioritization and load balancing in an extended LAN by means of path differentiation for traffic of different priorities. The present invention is also backward compatible with the IEEE 802.1D standard. The present invention supports multi-level traffic prioritization by extending the STAR Bridge Protocol to make use of hybrid forwarding paths as well as enhanced forwarding paths to forward frames in accordance with frame priorities. Since frames are forwarded over a plurality of alternate forwarding paths, the present invention also offers improved load balancing, thereby relieving congestion on certain tree links.